/*
 * 0570. 寻找丢失的数 II
 * 给一个由 1 - n 的整数随机组成的一个字符串序列，其中丢失了一个整数，请找到它。
 * https://www.lintcode.com/problem/find-the-missing-number-ii/description
 * 
 * 样例
 * 给出 n = 20, str = 19201234567891011121314151618
 * 丢失的数是 17 ，返回这个数。
 * 
 * 2018.06.22 @jeyming
 */
package find_the_missing_number_ii_0570;

public class Find_the_missing_number_ii_0570 {
	/**
     * @param n: An integer
     * @param str: a string with number from 1-n in random order and miss one number
     * @return: An integer
     */
    public static int findMissing2(int n, String str) {
        // write your code here
    	int[] cnt = new int[10];
    	int[] trueCnt = new int[10];
    	for(int i = 0; i < str.length(); ++i) {
    		++cnt[str.charAt(i) - '0'];
    	}
    	for(int i = 1; i <= n; ++i) {
    		if(i < 10) {
    			++trueCnt[i];
    		} else {
    			int tmp = i;
    			while(tmp > 0) {
    				++trueCnt[tmp % 10];
    				tmp /= 10;
    			}
    		}
    	}
    	int num = 0;
    	for(int i = 0 , j = 0; i < 10; ++i){
    		if(trueCnt[i] - cnt[i] == 1) {
    			num = num * j + i;
    			j += 10;
    		} else if(trueCnt[i] - cnt[i] == 2) {
    			return i * 10 + i;
    		}
    	}
    	if(num == 12){
    	    num = 21;
    	}
//    	for(int i = 1; i <= n; ++i) {
//    		if(i < 10) {
//    			if(cnt[i] == 0) {
//    				return i;
//    			} else {
//    				--cnt[i];
//    			}
//    		} else {
//    			int tmp = i;
//    			while(tmp > 0) {
//    				if(cnt[tmp % 10] == 0) {
//    					return i;
//    				} else {
//    					--cnt[tmp % 10];
//    				}
//    				tmp /= 10;
//    			}
//    		}
//    	}
    	return num;
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(findMissing2(20,"19201234567891011121314151618"));
		System.out.println(findMissing2(11,"111098765432"));
		System.out.println(findMissing2(28,"111098654327128213127262524232120191817161514"));
	}

}
